package cn.lishiyuan.leetcode;

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * 322. 零钱兑换
 * 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
 *
 * 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
 *
 * 你可以认为每种硬币的数量是无限的。
 *
 * 示例 1：
 *
 * 输入：coins = [1, 2, 5], amount = 11
 * 输出：3
 * 解释：11 = 5 + 5 + 1
 * 示例 2：
 *
 * 输入：coins = [2], amount = 3
 * 输出：-1
 * 示例 3：
 *
 * 输入：coins = [1], amount = 0
 * 输出：0
 *
 *
 * 提示：
 *
 * 1 <= coins.length <= 12
 * 1 <= coins[i] <= 231 - 1
 * 0 <= amount <= 104
 */
public class LeetCode322 {

    /**
     * 回溯法处理
     * @param coins
     * @param amount
     * @return
     */
    public static Map<Integer,Integer> coinChange(int[] coins, int amount) {
        if (amount <= 0) return Collections.emptyMap();

        int max = -1;
        Map<Integer,Integer> map = new HashMap<>();

        for (int coin : coins) {
            if (amount >= coin) {
                //尝试放入一枚后对剩余进行处理
                Map<Integer, Integer> integerIntegerMap = coinChange(coins, amount - coin);
                // 使用的硬币总数
                int sum = integerIntegerMap.values().stream().mapToInt(i -> i).sum();
                // 加上当前使用的一枚
                sum = sum + 1;

                // 取总数最小的
                if (max==-1 || sum < max){
                    max = sum;
                    map.clear();
                    map.putAll(integerIntegerMap);
                    Integer coinNum = map.getOrDefault(coin, 0);
                    map.put(coin,coinNum + 1);
                }
            }
        }


        int sum = map.entrySet().stream().mapToInt(d -> d.getKey() * d.getValue()).sum();

        if (sum != amount ) return Collections.emptyMap();

        return map;
    }


    /**
     * 动态规划
     * @param coins
     * @param amount
     * @return
     */
    public static Map<Integer,Integer> coinChangeDP(int[] coins, int amount) {
        // 由于每次金额只会增长，所以得到key之后可以逆向推出每个面额用了多时少
        // key已凑成的金额 value对应的最后一个硬币位置
        Map<Integer,Integer> dp = new HashMap<>();

        // 初始化
        for (int i=0 ;i<coins.length;i++) {
            if (amount >= coins[i]) {
                dp.put(coins[i],i);
            }
        }
        // 无法凑成
        if (dp.isEmpty()) return Collections.emptyMap();

        boolean find = false;

        // 上次状态，用来加速状态迁移过程，下次状态只与上次有关
        Map<Integer,Integer> before = new HashMap<>(dp);

        // 只有无法凑成或者已经凑成的情况下才会终止
        // 每次都对上次状态进行考察
        while (!find) {
            // 每次凑一张
            // 上次凑数的结果
            Set<Integer> amounts = before.keySet();
            // 本次凑数的结果
            Map<Integer,Integer> now = new HashMap<>();

            for (int i = 0; i < coins.length; i++) {
                // 上个状态的币值
                for (Integer a : amounts) {
                    int newAmount = coins[i] + a;
                    // 符合条件
                    if (newAmount <= amount) {
                        // 只保留最最小次数的金额
                        if (!dp.containsKey(newAmount)) {
                            // 不存在就存入，且需要继续寻找
                            // 可能存在重复，存在重复就不放入了
                            now.putIfAbsent(newAmount, i);
                        }
                        if (newAmount == amount) {
                            find = true;
                            // 已经找到
                            break;
                        }
                    }
                }
            }
            // 上次状态更新
            before = now;
            //存入本次的结果
            dp.putAll(now);
            // 无法凑出的情况
            if(now.isEmpty()) break;
        }

        Map<Integer,Integer> result = new HashMap<>();

        if (find){
            // 逆向推导出哪些面额用了多少
           int lease = amount;

           while (lease > 0){
               Integer index = dp.get(lease);
               Integer old = result.getOrDefault(index, 0);
               result.put(index,old+1);
               lease -= coins[index];
           }

        }

        return result;
    }


    /**
     * 动态规划 -- 状态转移方程
     * @param coins
     * @param amount
     * @return
     */
    public static Map<Integer,Integer> coinChangeDP2(int[] coins, int amount) {
        // 由于每次金额只会增长，所以得到key之后可以逆向推出每个面额用了多时少
        // key已凑成的金额 value对应的最后一个硬币位置
        Map<Integer,Integer> dp = new HashMap<>();

        // 初始化
        for (int i=0 ;i<coins.length;i++) {
            if (amount >= coins[i]) {
                dp.put(coins[i],i);
            }
        }
        // 无法凑成
        if (dp.isEmpty()) return Collections.emptyMap();

        // 上次状态，用来加速状态迁移过程，下次状态只与上次有关
        Map<Integer,Integer> before = new HashMap<>(dp);

        // 下次放入
        boolean find = coinChangeDP2(coins,amount,dp,before);

        if(!find){
            return Collections.emptyMap();
        }

        Map<Integer,Integer> result = new HashMap<>();
        // 逆向推导出哪些面额用了多少
        int lease = amount;

        while (lease > 0){
            Integer index = dp.get(lease);
            Integer old = result.getOrDefault(index, 0);
            result.put(index,old+1);
            lease -= coins[index];
        }

        return result;
    }

    /**
     * 动态规划 -- 状态转移方程
     * @param coins
     * @param amount
     * @return
     */
    private static boolean coinChangeDP2(int[] coins, int amount,Map<Integer,Integer> dp, Map<Integer,Integer> before) {
        // 每次凑一张
        // 上次凑数的结果
        Set<Integer> amounts = before.keySet();
        // 本次凑数的结果
        Map<Integer,Integer> now = new HashMap<>();

        for (int i = 0; i < coins.length; i++) {
            // 上个状态的币值
            for (Integer a : amounts) {
                int newAmount = coins[i] + a;
                // 符合条件
                if (newAmount <= amount) {
                    // 只保留最最小次数的金额
                    if (!dp.containsKey(newAmount)) {
                        // 不存在就存入，且需要继续寻找
                        // 可能存在重复，存在重复就不放入了
                        now.putIfAbsent(newAmount, i);
                    }
                    if (newAmount == amount) {
                        //存入本次的结果
                        dp.putAll(now);
                        return true;
                    }
                }
            }
        }

        // 无法凑出的情况
        if(now.isEmpty()) return false;
        //存入本次的结果
        dp.putAll(now);

        // 下次放入
        return coinChangeDP2(coins, amount, dp, now);
    }



}
